#include <iostream>
#include <vector>
#include <numeric>
#include <tuple>
#include <algorithm>
#ifdef _WIN32
#include <windows.h>
#endif
using namespace std;

struct DSU {
    vector<int> p, r;
    DSU(int n=0){ init(n); }
    void init(int n){ p.resize(n); r.assign(n,0); iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x]==x? x : p[x]=find(p[x]); }
    bool unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(r[a]<r[b]) swap(a,b); p[b]=a; if(r[a]==r[b]) r[a]++; return true; }
    bool same(int a,int b){ return find(a)==find(b); }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
#ifdef _WIN32
    // Ensure UTF-8 output/input in Windows console
    SetConsoleOutputCP(CP_UTF8);
    SetConsoleCP(CP_UTF8);
#endif
    // 演示：连通性查询 + 判环
    int n=7; // 0..6
    DSU dsu(n);
    vector<tuple<int,int>> edges = {
        {0,1},{1,2},{2,3},{4,5},{5,6},{2,0} // 最后一条使 0-1-2-0 成环
    };

    cout << "并查集演示：" << '\n';
    for(auto [u,v] : edges){
        bool merged = dsu.unite(u,v);
        cout << "加入边(" << u << "," << v << ") -> ";
        if(merged) cout << "合并成功";
        else cout << "检测到成环（同一集合）";
        cout << '\n';
    }

    cout << "\n连通性查询：" << '\n';
    vector<pair<int,int>> queries={{0,3},{0,4},{4,6},{1,6}};
    for(auto [a,b] : queries){
        cout << a << " 与 " << b << (dsu.same(a,b)? " 连通" : " 不连通") << '\n';
    }
    return 0;
}

